package org.myy.learn.hot.链表.相交链表;

public class Solution {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode PA = headA, PB = headB;
        while (PA != PB){
            PA = PA == null ? headB : PA.next;
            PB = PB == null ? headA : PB.next;
        }
        return PA;
    }

    private static ListNode build(int[] arr) {
        if (arr == null || arr.length == 0) return null;
        ListNode head = new ListNode(arr[0]), cur = head;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
        return head;
    }
    private static void linkByFirstCommonValue(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        while (pA != null) {
            ListNode pB = headB;
            while (pB != null) {
                if (pA.val == pB.val) {          // 找到值相同节点
                    // 把 pA 后续全部拼到 pB 上（或反之，只要保证是同一对象即可）
                    ListNode tailA = headA;
                    while (tailA.next != pA) tailA = tailA.next; // 找到 pA 前驱
                    tailA.next = pB;              // 拼成同一个引用
                    return;
                }
                pB = pB.next;
            }
            pA = pA.next;
        }
    }

    public static void main(String[] args) {
        ListNode headA = build(new int[]{1,9,1,2,4});
        ListNode headB = build(new int[]{3,2,4});
        linkByFirstCommonValue(headA, headB);
        System.out.println(getIntersectionNode(headA, headB).val);
    }
}
